H: Generátor bludísk
40 bodov	Časový limit: 500 ms

Je obedová prestávka a Lukáš si potrebuje oddýchnuť a vyventilovať hlavu. Preto si kúpil svoj obľúbený denník. Možno neviete, ale keď si Lukáš kúpi svoj obľúbený denník, nehľadá v ňom ani správy z domova, ani zo športu a ani z algoritmických súťaží. Nerieši ani trápne sudoku a nečíta si ani komix s Garfieldom. Áno, uhádli ste. Lukáš si ako prvé vždy pozrie bludisko a perom vyznačí cestu. V tejto úlohe by ste mali pomôcť redakcii týchto novín a naprogramovať jej generátor labyrintov, aby sme zabezpečili stabilný prínos inštancií tejto zaujímavej logickej disciplíny. Bludisko vyzerá napríklad takto:

#########
#.#S....#
#.###.#.#
#.....#.#
###.###.#
#C..#...#
#########

Bodka označuje chodbu, mriežka stenu. Krok sa dá spraviť medzi políčkami len vodorovne a zvislo (tzn. každé políčko má najviac štyroch susedov). Dĺžka cesty zo štartu (S) do cieľa (C) je v uvedenom prípade 10 krokov.

Na vstupe sú tri čísla: R, C a K (4 ≤ R,C ≤ 100, 1 ≤ K ≤ R·C). Výstupom vášho programu je bludisko, ktoré má rozmery R riadkov, C stĺpcov a najkratšia cesta zo štartu do cieľa má presne K krokov. Ak také bludisko neexistuje, máte vypísať NEDA SA. Presnejšie, pre bludisko na výstupe musí platiť:

• Všetky políčka na obvode bludiska musia byť steny.
• Nesmie existovať cesta zo štartu do cieľa, ktorá by bola kratšia ako K krokov.
• Musí existovať cesta zo štartu do cieľa, ktorá má K krokov.
• Nesmie obsahovať žiadny znak okrem spomenutých štyroch a znaky S a C musí obsahovať práve raz.
• Jeho plán musí pozostávať z práve R riadkov a C stĺpcov.

Vypíšte ľubovoľné bludisko spĺňajúce tieto požiadavky.

> Príklady:

vstup

5 5 5

výstup

##### #S..# ###.# ##C.# #####

vstup

10 8 22

výstup

######## #......# ##.###.# #C.#...# #####.## #......# #.####.# #.#S#..# #...#.## ########

vstup

10 8 44

výstup

NEDA SA

---